Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
xianyu
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定義hash table的結構
typedef struct {
int key; // 元素的值
int count; // 元素出現的次數
} HashTable;
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
// 1. 使用hash table統計每個元素的出現頻率
HashTable* hashTable = (HashTable*)malloc(numsSize * sizeof(HashTable)); // 分配hash table的空間
int hashTableSize = 0; // hash table的大小初始化為0
for (int i = 0; i < numsSize; i++) { // 遍歷數組
int found = 0; // 記錄當前元素是否已在hash table中
for (int j = 0; j < hashTableSize; j++) { // 遍歷hash table
if (hashTable[j].key == nums[i]) { // 如果元素已經在hash table中
hashTable[j].count++; // 增加其出現次數
found = 1; // 標記為已找到
break; // 結束當前loop
}
}
if (!found) { // 如果元素不在hash table中
hashTable[hashTableSize].key = nums[i]; // 將元素添加到hash table
hashTable[hashTableSize].count = 1; // 並設置其出現次數為1
hashTableSize++; // 增加hash table的大小
}
}
// 2. 使用bucket排序
int maxCount = numsSize; // 設定bucket數組的最大大小為數組的大小
int** buckets = (int**)malloc((maxCount + 1) * sizeof(int*)); // 分配bucket數組的空間
int* bucketSizes = (int*)calloc((maxCount + 1), sizeof(int)); // 初始化每個bucket的大小為0
// 計算每個bucket的大小
for (int i = 0; i < hashTableSize; i++) { // 遍歷hash table
int count = hashTable[i].count; // 取得當前元素的出現次數
bucketSizes[count]++; // 將對應bucket的大小加1
}
// 分配bucket的空間
for (int i = 0; i <= maxCount; i++) { // 遍歷每個bucket
if (bucketSizes[i] > 0) { // 如果bucket的大小大於0
buckets[i] = (int*)malloc(bucketSizes[i] * sizeof(int)); // 為bucket分配空間
bucketSizes[i] = 0; // 重置bucket的大小為0，用於之後存放元素
}
}
// 將元素放入bucket中
for (int i = 0; i < hashTableSize; i++) { // 遍歷hash table
int count = hashTable[i].count; // 取得當前元素的出現次數
buckets[count][bucketSizes[count]++] = hashTable[i].key; // 將元素放入對應頻率的bucket中
}
// 3. 收集結果
int* result = (int*)malloc(k * sizeof(int)); // 分配result 陣列的空間
*returnSize = 0; // 初始化返回的結果大小為0
for (int i = maxCount; i >= 0 && *returnSize < k; i--) { // 從後向前遍歷bucket數組
for (int j = 0; j < bucketSizes[i] && *returnSize < k; j++) { // 遍歷每個bucket中的元素
result[(*returnSize)++] = buckets[i][j]; // 將頻率最高的元素加入result
}
}
// 釋放memory
for (int i = 0; i <= maxCount; i++) { // 遍歷每個bucket
if (bucketSizes[i] > 0) { // 如果bucket的大小大於0
free(buckets[i]); // 釋放bucket的memory
}
}
free(buckets); // 釋放bucket數組的memory
free(bucketSizes); // 釋放bucket大小數組的memory
free(hashTable); // 釋放hash table的memory
return result;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定義hash table的結構
typedef struct {
int key; // 元素的值
int count; // 元素出現的次數
} HashTable;
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
// 1. 使用hash table統計每個元素的出現頻率
HashTable* hashTable = (HashTable*)malloc(numsSize * sizeof(HashTable)); // 分配hash table的空間
int hashTableSize = 0; // hash table的大小初始化為0
for (int i = 0; i < numsSize; i++) { // 遍歷數組
int found = 0; // 記錄當前元素是否已在hash table中
for (int j = 0; j < hashTableSize; j++) { // 遍歷hash table
if (hashTable[j].key == nums[i]) { // 如果元素已經在hash table中
hashTable[j].count++; // 增加其出現次數
found = 1; // 標記為已找到
break; // 結束當前loop
}
}
if (!found) { // 如果元素不在hash table中
hashTable[hashTableSize].key = nums[i]; // 將元素添加到hash table
hashTable[hashTableSize].count = 1; // 並設置其出現次數為1
hashTableSize++; // 增加hash table的大小
}
}
// 2. 使用bucket排序
int maxCount = numsSize; // 設定bucket數組的最大大小為數組的大小
int** buckets = (int**)malloc((maxCount + 1) * sizeof(int*)); // 分配bucket數組的空間
int* bucketSizes = (int*)calloc((maxCount + 1), sizeof(int)); // 初始化每個bucket的大小為0
// 計算每個bucket的大小
for (int i = 0; i < hashTableSize; i++) { // 遍歷hash table
int count = hashTable[i].count; // 取得當前元素的出現次數
bucketSizes[count]++; // 將對應bucket的大小加1
}
// 分配bucket的空間
for (int i = 0; i <= maxCount; i++) { // 遍歷每個bucket
if (bucketSizes[i] > 0) { // 如果bucket的大小大於0
buckets[i] = (int*)malloc(bucketSizes[i] * sizeof(int)); // 為bucket分配空間
bucketSizes[i] = 0; // 重置bucket的大小為0，用於之後存放元素
}
}
// 將元素放入bucket中
for (int i = 0; i < hashTableSize; i++) { // 遍歷hash table
int count = hashTable[i].count; // 取得當前元素的出現次數
buckets[count][bucketSizes[count]++] = hashTable[i].key; // 將元素放入對應頻率的bucket中
}
// 3. 收集結果
int* result = (int*)malloc(k * sizeof(int)); // 分配result 陣列的空間
*returnSize = 0; // 初始化返回的結果大小為0
for (int i = maxCount; i >= 0 && *returnSize < k; i--) { // 從後向前遍歷bucket數組
for (int j = 0; j < bucketSizes[i] && *returnSize < k; j++) { // 遍歷每個bucket中的元素
result[(*returnSize)++] = buckets[i][j]; // 將頻率最高的元素加入result
}
}
// 釋放memory
for (int i = 0; i <= maxCount; i++) { // 遍歷每個bucket
if (bucketSizes[i] > 0) { // 如果bucket的大小大於0
free(buckets[i]); // 釋放bucket的memory
}
}
free(buckets); // 釋放bucket數組的memory
free(bucketSizes); // 釋放bucket大小數組的memory
free(hashTable); // 釋放hash table的memory
return result;
}
// 測試函數
int main() {
int nums1[] = {1, 1, 1, 2, 2, 3}; // 測試數據1
int nums2[] = {1}; // 測試數據2
int returnSize; // 用於存儲返回結果的大小
int* result1 = topKFrequent(nums1, 6, 2, &returnSize); // 求前2個最常出現的元素
printf("Top 2 frequent elements: ");
for (int i = 0; i < returnSize; i++) { // 輸出結果
printf("%d ", result1[i]);
}
printf("\n");
free(result1); // 釋放結果數組的memory
int* result2 = topKFrequent(nums2, 1, 1, &returnSize); // 求前1個最常出現的元素
printf("Top 1 frequent element: ");
for (int i = 0; i < returnSize; i++) { // 輸出結果
printf("%d ", result2[i]);
}
printf("\n");
free(result2); // 釋放結果數組的memory
return 0;
}
iThome鐵人賽
看影片追技術